In recent years, various types of code-cracking methods have been proposed for analyzing an encryption key with use of side information of encryption processing performed by an encryption module realized with hardware or software. These code-cracking methods allow an unauthorized third person to analyze an encryption key to crack a private key, and pretend to be an authorized user using the cracked private key to perform an unauthorized act using the private key.
One example of such code-cracking methods is a timing attack in which an encryption key is analyzed with use of the fact that a period necessary for an encryption module to perform encryption processing slightly varies depending on a value of the encryption key used for the encryption processing. That is, according to the timing attack, an encryption key is analyzed using a period necessary for performing encryption processing as side information. Code-cracking methods using side information include the Simple Power Analysis and the Differential Power Analysis in which an encryption key is analyzed using an amount of power consumed for performing encryption processing as side information. With high-performance measurement devices that are obtainable inexpensively in recent years, these code-cracking methods are known to be capable of analyzing actual products provided with an encryption module such as IC cards. In the following descriptions, code-cracking methods of analyzing an encryption key with use of the change in an amount of power consumed for encryption processing by an encryption module as described above, that is, a power waveform are collectively referred to as “power analysis attacks”. Note that timing attacks are described in detail in the Non-Patent Document 1, and power analysis attacks are described in detail in the Non-Patent Document 2.
The following describes the Simple Power Analysis of the RSA encryption. Note that the RSA encryption is described in detail in the Non-Patent Document 3.
<Simple Power Analysis of RSA Encryption>
In a case where decryption processing is performed based on the RSA encryption scheme, with respect to a product n of primes p and q, a ciphertext c that is a positive integer less than n, and a private key d that is a positive integer, c^d mod n is calculated. As a method of calculating this expression, the binary method disclosed in page 9 of the Non-Patent Document 4 is known, for example. The following describes the binary method. When d=d0+d1×2+d2×2^2+ . . . +d(len−1)×2^(len−1) and i=0, 1, . . . , len−1 are satisfied, di is 0 or 1. Here, len denotes the number of bits of d, and “×” denotes multiplication of integers, and “x^y” denotes x raised to the y-th power.
(Binary Method)
Step 1-1: i←len−2 and z←c
Step 1-2: z←z^2 mod n
Step 1-3: Judge whether di is 1.                When di=1, z←z×c mod n.        
Step 1-4: i←i−1 Judge whether i is negative. When i is negative, output z. Otherwise, return to Step 1-2.
According to the above method, Steps 1-2, 1-3, and 1-4 are repeatedly performed as a loop. In this loop, with respect to di (i=1, 2, . . . , len−1) in a case where di=1, square of z and multiplication of c are performed. With respect to di (i=1, 2, . . . , len−1) in a case where di=0, only square of z is performed. The value n is a large value such as an integer of 1024 bits. Generally, square can improve the efficiency in calculation processing compared with multiplication. Accordingly, it is possible to perform processing in a case where di=0 at a higher speed than that in a case where di=1. In such a case, square and multiplication differ in processing from each other, and accordingly differ in power waveform from each other.
Therefore, measurement of power waveforms makes it possible to analyze a calculation order in which square and multiplication are performed. Furthermore, by using the fact that calculation processing performed in the loop differs depending on a value of di, it is possible to obtain a value of di based on the calculation order in which calculation processing is performed. As a result, it is possible to perform the Simple Power Analysis by performing the following steps.
(Simple Power Analysis Using Binary Method)
Step 2-1: Decrypt a ciphertext c, and measure power waveforms consumed for decrypting the ciphertext c.
Step 2-2: Obtain the calculation order in which square and multiplication are performed based on the above power waveforms.
Step 2-3: Obtain a bit di (i=1, 2, . . . , len−1) based on the above calculation order.
<Conventional Countermeasure Against Simple Power Analysis of RSA Encryption>
According to the above Simple Power Analysis, a private key is analyzed by using the fact that multiplication is performed only when di=1 in Step 1-3 of the binary method.
In view of this, the following countermeasure has been proposed against the Simple Power Analysis. According to this countermeasure, when di=0, z is multiplied by 1. A result of this multiplication remains z. However, by performing multiplication even when di=0, the calculation order in which square and multiplication are performed does not depends on whether di is 0 or 1 (see the Non-Patent Document 1).
According to the above countermeasure against the Simple Power Analysis of the RSA encryption, when di=1, a value c is used for multiplication. Also, when di=0, a value 1 is used for multiplication. In this way, a multiplier differs depending on whether di is 0 or 1. With use of this, there has been proposed an attack of analyzing whether di is 0 or 1 (referred to as “Big Mac Attack”) (see the Non-Patent Document 5). This Big Mac Attack enables analysis on whether di is 0 or 1 even if the above countermeasure against the Simple Power Analysis is taken. This is because power waveforms consumed for performing multiplications using the same multiplier are likely to partially match each other. Accordingly, it is possible to classify power waveforms consumed for performing multiplications into two types (for example, a group A and a group B), which are acquired by performing the Simple Power Analysis. There are only two correspondence patterns including a pattern in which the group A corresponds to di=1 and the group B corresponds to di=0, and a pattern in which the group A corresponds to di=0 and the group B corresponds to di=1. By newly decrypting a ciphertext with respect to each of the two patterns for example, it is possible to find which of the two patterns is correct, that is, it is possible to obtain a private key.
In view of this, the Patent Document 1 discloses an art for making analysis of a private key difficult. According to this art, a private key d is divided into a plurality of blocks each having predetermined bits. A value z is multiplied by a random value different for each block based on the binary method regardless of a value of di. Then, after squares and multiplications complete with respect to all the values as di, a random value used for the multiplications is cancelled using a cancellation value corresponding to the random value.
According to the Patent Document 1, before c^d for a ciphertext c is calculated, values R and S are calculated. Here, R×S mod n=1.
Then, square and multiplication for each of values as di are performed. Here, random values to be used for multiplication are determined using a value R such that the random values are different for each block. For example, with respect to the m-th block, multiplication is performed using a random value R^m. Accordingly, it is possible to use random values different for each block.
After squares and multiplications complete with respect to all the blocks, an influence of the random value R is cancelled by using a value S. This results in a value c^d.
According to this art, there are two correspondence patterns including a pattern in which di=0 and a pattern in which di=1 for each block. Since there are two correspondence patterns for each of all the blocks, there are 2^(the number of blocks) patterns for the whole private key d. Accordingly, an analyzer needs to check all the 2^(the number of blocks) patterns. This makes analysis of a private key difficult.    [Patent Document 1] Japanese Laid-Open Patent Application Publication No. 2000-165375    [Non-Patent Document 1] Paul Kocher. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In Neal Koblitz, editor, CRYPTO'96, LNCS1109, Springer-Verlag, 1996, pp. 104-113    [Non-Patent Document 2] P. Kocher, J. Ja_e, and B. Jun, “Di_erential Power Analysis”, Advances in Cryptology-CRYPTO '99, LNCS, 1666, Springer-Verlag, 1999, pp. 388-397    [Non-Patent Document 3] Tatsuaki OKAMOTO, Hirosuke YAMAMOTO “Gendai Ango” (Modern Cryptography), Sangyotosho (1997)    [Non-Patent Document 4]H. Cohen, “A Course in Computational Algebraic Number Theory”, GTM 138, Springer-Verlag, 1996, p 9    [Non-Patent Document 5] C. D. Walter, “Sliding windows succumbs to Big Mac Attack”, CHES2001, LNCS2162, Springer-Verlag, 2001, pp. 286-299    [Non-Patent Document 6] Kaminaga, Watanabe, Endoh, OhKohchi, “Power Analysis and Countermeasure of RSA Cryptosystem”, IEICE, Vol. J88-A, No. 5, pp. 606-615, 2005